package net.cyndeline.rlgraph.biconnectivity.components

import scalax.collection.immutable.Graph
import scala.collection.mutable
import scalax.collection.GraphEdge.UnDiEdge
import net.cyndeline.rlgraph.biconnectivity.BiconnectedComponentsOperation

/**
 * Computes all biconnected components from a graph.
 */
class DFSComponentSearch[VType, EType[X] <: UnDiEdge[X]] extends BiconnectedComponentsOperation[VType, EType] {
  private var count = 0
  private val vertexInfo = new mutable.HashMap[Graph[VType, EType]#NodeT, VertexInfo]()

  /**
   * Computes a list of biconnected components from a connected graph by using a DFS search.
   * @param graph A connected undirected graph.
   * @return A list of every biconnected component in the graph. If the graph is empty or only
   *         has one vertex, an empty list is returned.
   */
  def components(graph: Graph[VType, EType]): List[Graph[VType, EType]] = {
    var result: List[Graph[VType, EType]] = Nil
    count = 0
    vertexInfo.clear()

    /* Add info to every vertex. */
    for (vertex <- graph.nodes) {
      vertexInfo += (vertex -> new VertexInfo(vertex))
    }

    for (vertex <- graph.nodes) {
      val info: VertexInfo = vertexInfo(vertex)

      if (!info.visited) {
        result = result ++ dfsVisit(vertex, graph)
      }
    }

    result
  }

  private def dfsVisit(vertex: Graph[VType, EType]#NodeT, graph: Graph[VType, EType], stack: mutable.Stack[Graph[VType, EType]#EdgeT] = new mutable.Stack()): List[Graph[VType, EType]] = {
    val info: VertexInfo = vertexInfo(vertex)
    count = count + 1
    var currentResult: List[Graph[VType, EType]] = Nil
    info.visited = true
    info.num = count
    info.low = info.num

    val neighbors: Iterator[Graph[VType, EType]#EdgeT] = vertex.incoming.iterator
    while(neighbors.hasNext) {
      val neighbor: Graph[VType, EType]#EdgeT = neighbors.next()
      val nEdge: EType[VType] = neighbor.toOuter

      /* In these compairsons, == must be called on vertex with the edge value as parameter, or it will yield false. */
      val neighborVertex: Graph[VType, EType]#NodeT = if (vertex == nEdge._1) graph.get(nEdge._2) else if (vertex == nEdge._2) graph.get(nEdge._1) else throw new Error("The edge belonged to neither vertex")
      val neighborInfo: VertexInfo = vertexInfo(neighborVertex)

      if (!neighborInfo.visited) {
        stack.push(neighbor)
        neighborInfo.parent = Option(vertex)

        currentResult = currentResult ++ dfsVisit(neighborVertex, graph, stack)

        if (neighborInfo.low >= info.num) {
          currentResult = currentResult :+ constructComponent(nEdge, stack, graph)
        }

        info.low = Math.min(info.low, neighborInfo.low)

      } else if (info.parent.isDefined && info.parent.get != neighborVertex && neighborInfo.num < info.num) {
        stack.push(neighbor)
        info.low = Math.min(info.low, neighborInfo.num)
      }
    }

    currentResult
  }

  private def constructComponent(stop: EType[VType], stack: mutable.Stack[Graph[VType, EType]#EdgeT], constructTemplate: Graph[VType, EType]): Graph[VType, EType] = {
    var graph = constructTemplate.empty
    var top: Option[Graph[VType, EType]#EdgeT] = None

    do {
      top = Some(stack.pop())
      graph = graph + top.get
    } while (top.get != stop)

    graph
  }

  private class VertexInfo(val vertex: VType) {
    var visited = false
    var num = 0
    var low = 0
    var parent: Option[Graph[VType, EType]#NodeT] = None
  }
}
